﻿#pragma once

#include <functional>
#include <vector>

namespace xy
{

namespace utils
{

/**
 * @brief 二分查找
 *
 * @tparam T
 * @param[in] t
 * @param[in] size
 * @param[in] key
 * @return std::size_t
 */
template <class T> inline std::size_t binary_search(const T *t, std::size_t size, T key)
{
    std::size_t left = 0, right = size, mid = 0;
    while (left < right)
    {
        mid = (left + right) / 2;
        if (t[mid] == key)
            return mid;
        else if (t[mid] < key)
            left = mid + 1;
        else
            right = mid;
    }
    return left;
}

/**
 * @brief 冒泡排序
 *
 * @tparam T
 * @param[in] t
 * @param[in] size
 */
template <class T> inline void bubble_sort(T *t, std::size_t size)
{
    for (std::size_t i = 0; i < size; i++)
    {
        for (std::size_t j = i + 1; j < size; j++)
        {
            if (t[i] > t[j])
                std::swap(t[i], t[j]);
        }
    }
}

/**
 * @brief 插入排序
 *
 * @tparam T
 * @param[in] t
 * @param[in] size
 */
template <class T> inline void insert_sort(T *t, std::size_t size)
{
    for (std::size_t i = 1; i < size; i++)
    {
        std::size_t k = i;
        for (int j = i - 1; j >= 0; j--)
        {
            if (t[i] < t[j])
                k = j;
        }

        // 整体向后移动
        T val = t[i];
        for (int j = i; j > k; j--)
            t[j] = t[j - 1];
        t[k] = val;
    }
}

/**
 * @brief 二分插入排序
 *
 * @tparam T
 * @param[in] t
 * @param[in] size
 */
template <class T> inline void binary_insert_sort(T *t, std::size_t size)
{
    for (std::size_t i = 1; i < size; i++)
    {
        // 二分查找插入位置
        std::size_t k = binary_search(t, i, t[i]);

        // 整体向后移动
        T val = t[i];
        for (int j = i; j > k; j--)
            t[j] = t[j - 1];
        t[k] = val;
    }
}

/**
 * @brief 希尔排序
 *
 * @tparam T
 * @param[in] t
 * @param[in] size
 */
template <class T> inline void shell_sort(T *t, std::size_t size)
{
    // 每次间隔减半
    std::size_t step = size / 2;
    while (step > 0)
    {
        // 分组
        std::size_t first = 0;
        while (first < step)
        {
            // 对每一组插入排序
            for (std::size_t j = 1; first + j * step < size; j++)
            {
                std::size_t k = j;
                for (int i = j - 1; i >= 0; i--)
                {
                    if (t[first + j * step] < t[first + i * step])
                        k = i;
                }

                T val = t[first + j * step];
                for (int i = j; i > k; i--)
                    t[first + i * step] = t[first + i * step - step];
                t[first + k * step] = val;
            }
            first++;
        }
        step /= 2;
    }
}

/**
 * @brief 归并排序
 *
 * @tparam T
 * @param[in] t
 * @param[in] size
 * @param[in] i
 */
template <class T> inline void merge_sort(T *t, std::size_t size, std::size_t i = 0)
{
    std::vector<T> AB, BC;
    if (size > i + 1)
    {
        std::size_t mid = (size + i) / 2;
        merge_sort(t, mid, i);
        merge_sort(t, size, mid);

        // 归并数组
        std::size_t a = i;
        std::size_t b = mid;
        std::size_t c = size;

        // 记录两个数组的开头
        std::size_t ab_id = 0;
        std::size_t bc_id = 0;

        // 定义两个数组
        AB.resize(b - a + 1);
        BC.resize(c - b + 1);

        // 记录最大值
        T max = 0;
        for (std::size_t j = a; j < b; j++)
        {
            AB[j - a] = t[j];
            max = std::max(max, t[j]) + 1;
        }

        for (std::size_t j = b; j < c; j++)
        {
            BC[j - b] = t[j];
            max = std::max(max, t[j]) + 1;
        }

        // 最后一位存放最小值，用作边界
        AB[b - a] = BC[c - b] = max;

        for (std::size_t j = a; j < c; j++)
        {
            if (AB[ab_id] < BC[bc_id])
            {
                t[j] = AB[ab_id];
                ab_id++;
            }
            else
            {
                t[j] = BC[bc_id];
                bc_id++;
            }
        }
    }
}

/**
 * @brief 快速排序
 *
 * @tparam T
 * @param[in] t
 * @param[in] size
 * @param[in] i
 */
template <class T> inline void quick_sort(T *t, std::size_t size, std::size_t i = 0)
{
    if (size > i + 1)
    {
        T choice = t[i];
        int left = (int)i - 1, right = size;
        while (left < right)
        {
            do
            {
                left++;
            } while (t[left] < choice);
            do
            {
                right--;
            } while (t[right] > choice);
            if (left < right)
                std::swap(t[left], t[right]);
        }

        // 分治
        quick_sort(t, right + 1, i);
        quick_sort(t, size, right + 1);
    }
}

/**
 * @brief 假设 i 元素是新加入的元素，执行降堆
 *
 * @tparam T
 * @tparam Ty
 * @param[in] t
 * @param[in] size
 * @param[in] i
 */
template <class T, typename Ty = std::greater<T>> inline void push_heap(T *t, std::size_t size, std::size_t i = 0)
{
    std::size_t l = ((((i) + 1) << 1) - 1); // left child
    std::size_t r = (((i) + 1) << 1);       // right child
    std::size_t result = i;

    // 定义比较对象
    Ty compare;
    if (l < size && compare(t[l], t[result]))
        result = l;
    if (r < size && compare(t[r], t[result]))
        result = r;
    // 如果 result 对应的元素不在正确的位置上就交换
    if (result != i)
    {
        std::swap(t[i], t[result]);
        push_heap(t, size, result);
    }
}

/**
 * @brief 将头部元素移动到末尾，剩余元素建堆
 *
 * @tparam T
 * @tparam Ty
 * @param[in] t
 * @param[in] size
 * @return T
 */
template <class T, typename Ty = std::greater<T>> inline T pop_heap(T *t, std::size_t size)
{
    std::swap(t[size - 1], t[0]);
    push_heap(t, --size, 0);
    return t[size];
}

/**
 * @brief 数组建堆
 *
 * @tparam T
 * @tparam Ty
 * @param[in] t
 * @param[in] size
 */
template <class T, typename Ty = std::greater<T>> inline void make_heap(T *t, std::size_t size)
{
    // 建堆，重复降堆，实现最大堆
    auto parent = [](std::size_t i) { return ((((i) + 1) >> 1) - 1); };
    for (int i = parent(size - 1); i >= 0; i--)
        push_heap(t, size, i);
}

/**
 * @brief 堆排序
 *
 * @tparam T
 * @tparam Ty
 * @param[in] t
 * @param[in] size
 */
template <class T, typename Ty = std::greater<T>> inline void heap_sort(T *t, std::size_t size)
{
    for (int i = size - 1; i > 0; i--)
        pop_heap(t, size--);
}

} // namespace utils

} // namespace xy
